#include "bits/stdc++.h"
using namespace std;


const int maxn=2e5+10;
const int maxm=1e6+10;
vector<int> G[maxm];
int t,n,a[maxn],rec[maxn],b[maxn],L,clr[maxn],ans,tmp,tmp2;

int main()
{
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	cin>>t;
	while(t--)
	{
		ans=0;
		memset(clr,0,sizeof(clr));
		cin>>n;
		for(int i=1;i<=n;i++) 
		{
			cin>>a[i];
			rec[i]=a[i];
		}
		sort(a+1,a+1+n);
		L=unique(a+1,a+1+n)-a-1;
		for(int i=1;i<=n;i++)
		{
			int p=upper_bound(a+1,a+1+L,rec[i])-a-1;
			b[i]=p;
		}
		//
//		for(int i=1;i<=n;i++) cout<<b[i]<<" ";
//		cout<<endl;
		//
		for(int i=1;i<=n;i++)
			G[b[i]].push_back(i);
		for(int i=L;i>=1;i--)
		{
			cout<<"i:"<<i<<" ";
			for(int i=1;i<=n;i++) cout<<clr[i];
			cout<<endl;
			if(G[i].size()>=2)
			{
//				cout<<i<<endl;
				int len=G[i].size();
				for(int j=0;j<len-1;j++)
				{
					int clr1=G[i][j];
					int clr2=G[i][j+1];
					if(!clr[clr1]&&!clr[clr2])
					{
						int dif=0;
						for(int k=clr1+1;k<clr2-1;k++)
						{
							if(clr[k]!=clr[k+1]) dif=1;
						}
						if(!dif)
						{
							if(clr[clr1+1]==0)
							{
								clr[clr1]=2;
								clr[clr2]=2;
								for(int k=clr1+1;k<clr2;k++)
									clr[k]=1;
							}
							else 
							{
								tmp=0;
								if(clr[clr1+1]==1) tmp=2;
								else tmp=1;
								clr[clr1]=tmp;
								clr[clr2]=tmp;
							}
							ans+=i;
						}
					}
					else if((!clr[clr1]&&clr[clr2])||(clr[clr1]&&!clr[clr2]))
					{
						if(clr[clr1]) tmp=clr[clr1];//liang duan yan se
						else tmp=clr[clr2];
						if(tmp==1) tmp2=2;//liang duan fan yan se
						else tmp2=1;
						int flag=0;
						for(int i=clr1+1;i<clr2;i++)
						{
							if(!clr[i]) clr[i]=tmp2;
							else if(clr[i]==tmp) flag=1;
						}
						if(!flag) ans+=i; 
					}
					else 
					{
						if(clr[clr1]==clr[clr2])
						{
							int hcz=0;
							for(int i=clr1+1;i<clr2-1;i++)
							{
								if(clr[i]!=clr[i+1]) hcz=1;
							}
							if(!hcz) ans+=i;
						}
					}
				}
			}	
		}
		for(int i=1;i<=L;i++) G[i].clear();
		cout<<ans<<endl;
	}
	return 0;
}
